1. Field of the Invention
This invention relates generally to multiple processor computer systems and more particularly to cache coherence in such systems.
2. Description of the Background Art
Multiple-processor computer systems involve various processors which at the same time may each work on a separate portion of a problem or work on a different problem. FIG. 1 shows a multi-processor system, including a plurality of Central Processing Units (CPUs) or processors 102A, 102B . . . 102N, communicating with memory 104 via interconnect 106, which could be, for example, a bus or a collection of point-to-point links. Processors 102 access data from memory 104 for a read or a write. In a read operation, processor 102 receives data from memory 104 without modifying the data, while in a write operation processor 102 modifies the data transmitted to memory 104.
Each processor 102 generally has a respective cache unit 108A, 108B, . . . 108N, which is a relatively small group of high speed memory cells dedicated to that processor. A processor 102""s cache 108 is usually on the processor chip itself or may be on separate chips, but is local to processor 102. Cache 108 for each processor 102 is used to hold data that was accessed recently by that processor. Since a processor 102 does not have to go through the interconnecting bus 106 and wait for the bus 106 traffic, the processor 102 can generally access data in its cache 108 faster than it can access data in the main memory 104. In a normal operation, a processor 102N first reads data from memory 104 and copies that data to the processor""s own cache 108N. During subsequent accesses for the same data the processor 102N fetches the data from its own cache 108N. In effect, after the first read, data in cache 108N is the same copy of data in memory 104 except that the data is now in a high-speed local storage. Typically, cache 108N can be accessed in one or two cycles of CPU time while it takes a processor 102 15 to 50 cycles to access memory 104. A typical processor 102 runs at about 333 Mhz or 3 ns (nanoseconds) per cycle, but it takes at least 60 ns or 20 cycles to access memory 104.
A measure of data, typically 32, 64, 128, or 2n bytes, brought from memory 104 to cache 108 is usually called a xe2x80x9ccache line.xe2x80x9d The data of which a copy was brought to cache 108 and which remains in memory 104 is called a xe2x80x9cmemory line.xe2x80x9d The size of a cache line or a memory line is determined by a balance of the overhead per read/write operation versus the usual amount of data transferred from memory and cache. An efficient size for a cache line results in transfers spending about 25% of their time on overhead and 75% of their time on actual data transfer.
A particular problem with using caches is that data becomes xe2x80x9cstale.xe2x80x9d A first processor 102A may access data in the main memory 104 and copy the data into its cache 108A. If the first processor 102A then modifies the cache line of data in its cache 108A, then at that instant the corresponding memory line becomes stale. If a second processor, 102B for example, subsequently accesses the original data in the main memory 104, the second processor 102B will not find the most current version of the data because the most current version is in the cache 108A. For each cache-line address, cache coherence guarantees that only one copy of data in cache 108 can be modified. Identical copies of a cache line may be present in multiple caches 108, and thus be read by multiple processors 102 at the same time, but only one processor 102 is allowed to write, i.e., modify, the data. After a processor 102 writes to its cache 108 that processor 102 must xe2x80x9cinvalidatexe2x80x9d any copies of that data in other caches to notify other processors 102 that their cache lines are no longer current.
FIG. 2A shows valid cache lines D0 for caches 108A to 108N whereas FIG. 2B shows cache 108B with an updated cache line D1 and other caches 108A, 108C, and 108N with invalidated cache lines D0. The processors 102A, 102C, and 102N with invalidated cache data D0 in their respective caches 108 must fetch the updated version of cache line D1 if they want to access that data line again.
Normally and for illustrative purposes in the following discussion, cache coherence protocols are executed by processors 102 associated with their related caches. However, in other embodiments these protocols may be executed by one or more specialized and dedicated cache controllers.
There are different cache coherence management methods for permitting a processor 102 to modify its cache line in cache 108 and invalidate other cache lines. One method (related to the present invention) utilizes, for each cache line, a respective xe2x80x9cshared listxe2x80x9d representing cache-line correspondences by xe2x80x9cdouble-linksxe2x80x9d where each cache has a forward pointer pointing to the next cache entry in the list and a backward pointer pointing to the previous cache entry in the list. Memory 104 has a pointer which always points to the head of the list.
FIG. 3 shows a linked list 300 of caches 108A . . . 108N with the associated memory 104. Memory 104 has a pointer which always points to the head (cache 108A) of the list while the forward pointers Af, Bf, and Cf of caches 108A, 108B, and 108C respectively point forward to the succeeding caches 108B, 108C, and 108D (not shown). Similarly, backward pointers Nb, Cb, and Bb of caches 108N, 108C, and 108B respectively point backward to the preceding caches. Because each cache unit 108 is associated with a respective processor 102, a linked list representation of cache 108 is also understood as a linked list representation of processors 102.
There are typically two types of cache sharing list. The first type list is the read-only (sometimes called xe2x80x9cfreshxe2x80x9d) list of caches for-which none of the processors 102 has permission to modify the data. The second type list is a read-write (sometimes called xe2x80x9cownedxe2x80x9d) list of caches for which the head-of-list processor 102 may have permission to write to its cache 108. A list is considered xe2x80x9cstablexe2x80x9d after an entry has been completely entered into or completely deleted from the list. Each of the stable list states is defined by the state of the memory and the states of the entries in the shared list. Relevant states of memory include HOME, FRESH, and STALE. HOME indicates no shared list exists, FRESH indicates a read-only shared list, and STALE indicates the shared list is a read-write list and data in the list can be modified. A processor 102 must get authorization to write to or read from memory 104. A list entry always enters the list as the list head, and the action of entering is referred to as xe2x80x9cprependingxe2x80x9d to the list. If a list is FRESH (the data is the same as in memory), the entry that becomes the newly created head receives data from memory; otherwise it receives data from the previous list head. In a read-write list, only the head is allowed to modify (or write to) its own cache line and, after the head has written the data, the head must invalidate the other stale copies of the shared list. In one embodiment, invalidation is done by purging the pending invalidated entries of the shared list.
FIGS. 4A-4F illustrate how the two types of list are created and grown. Each of the FIGS. 4 includes a before and an after list with states of the list and memory 104. In FIG. 4A, initially memory 104 is in the HOME state, indicating there is no cache shared list. Processor 102A requests permission to read a cache line. Since this is a read request, memory 104 changes from the HOME state to the FRESH state, and the resulting after list 402AR is a read-only list with one entry 108A. Cache 108A receives data from memory 104 because cache 108A accesses data that was previously uncached. This starts the read-only list 402AR.
In FIG. 4B processor 102B requests a read permission to enter the read-only list 402B, which is the same list as 402AR of FIG. 4A. Cache 108B then becomes the head of the list 402BR receiving data line from head 108A. The list 402BR is still a read-only list since both entries of the list have asked for read-only permission, and therefore the memory state remains FRESH.
In FIG. 4C, memory 104 is initially in the HOME state and processor 102A requests a read-write permission. Cache 108A then becomes the head of the list 402CR. Because a read-write permission was requested, list 402CR is a read-write list. As soon as memory 104 grants a read-write permission, memory 104 changes from the HOME state to the STALE state.
In FIG. 4D processor 102B requests a read permission to enter a read-write list 402D. Cache 108B becomes the head of the list 402DR. Since memory 104 is initially in the STALE state, the resulting list 402DR is a read-write list and memory 104 remains in the STALE state.
In FIG. 4E, the initial list 402E is read-only with memory 104 in the FRESH state, and processor 102B requests a write permission. Cache 108B then becomes the head of the list 402ER. Since processor 102B asked for a write permission, memory 104 changes state from FRESH to STALE, and list 402ER is a read-write list.
In FIG. 4F the list 402F is a read-write list and processor 102B requests a write permission. Since list 402F is read-write, list 402FR is also read-write, and memory 104 remains in the STALE state.
Cache list entries may be deleted. However, deleting a head-of-list presents a problem in mixed-coherence protocols, which exist where processor 102 associated with the head of the list supports a read-only option while processor 102 associated with the next-list entry supports only a read-write option. Currently most multi-processor systems support read-write lists and read-only lists are optional.
To update from a read-only list to a read-write list, the head of the list requests a read-write permission from memory 104 in the same way as any other cache entry would do. During the updating transaction if another cache has joined the list the head may end up in two places in the list. However, prior art solutions would not allow such a condition to exist. A transaction attempting to change a head from read-only to read-write would be aborted if a new entry had joined the list. A distinct abort scheme is therefore needed, requiring waiting for the expected prepend and then converting from a non-head to a read-write head.
In light of the deficiencies of prior art solutions, the present invention provides a system and method for updating a head of a cache coherence list from read-only to read-write. The invention allows two copies of one cache entry to exist in a list, and permits the list to expand. To update a head, a request is initiated. If a cache entry enters the list while an updating transaction is in progress, the invention allows there to be two cache copies having two distinct states, one read-only and one read-write, at different places in the list. One group of cache entries (the read-only group) enters the list by prepending to the read-only copy while another group of cache entries (the read-write group) enters the list by prepending to the read-write copy. During prepending, coded cache-to-cache command sets are implemented for the two read-only and read-write groups to distinctly communicate with the preperded cache entry. The read-only group possesses a command_F set (xe2x80x9cFxe2x80x9d for fresh or read-only) and the read-write group acquires a command_S set (xe2x80x9cSxe2x80x9d for state or read-write). The read-only group is then prepended to enter the list while the read-write group waits. The cache head is modified and invalidation follows. Finally the read-write group is prepended.